package solution;

import common.UnionFind;

/**
 * @author zhangmin
 * @create 2021-09-26 16:38
 */
public class Solution_10UF {

    /*===========================================================================================================================
     *130. 被围绕的区域
     * 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     * 1.先用 for 循环遍历棋盘的四边，用 DFS 算法把那些与边界相连的 O 换成一个特殊字符，比如 #；然后再遍历整个棋盘，把剩下的 O 换成 X，把 # 恢复成 O。这样就能完成题目的要求，时间复杂度 O(MN)。
     * 2.UF
     *  */
    int n,m;
    public void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] !='O') {
            return;
        }
        board[x][y] = 'A';

        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
    public void solve(char[][] board) {
        n=board.length;
        if (n==0)return;
        m= board[0].length;
        if (m==0) return;
        //遍历左右两条边界
        for (int i = 0; i < n; i++) {
            dfs(board,i,0);
            dfs(board,i,m-1);
        }
        //遍历上下两条边界
        for (int i = 0; i < m; i++) {
            dfs(board,0,i);
            dfs(board,n-1,i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j]=='A') {
                    board[i][j] = 'O';
                } else if (board[i][j]=='O'){
                    board[i][j]='X';
                }
            }
        }
    }


    //2.UF
    void solve1(char[][] board) {
        if (board.length == 0) return;
        int n = board.length;
        int m = board[0].length;
        // 给 dummy 留一个额外位置
        UnionFind uf = new UnionFind(n * m + 1);
        int dummy = m * n;
        // 将首列和末列的 O 与 dummy 连通
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O')
                uf.union(i * m, dummy);
            if (board[i][m - 1] == 'O')
                uf.union(i * m + m - 1, dummy);
        }
        // 将首行和末行的 O 与 dummy 连通
        for (int i = 0; i < m; i++) {
            if (board[0][i] == 'O')
                uf.union(i, dummy);
            if (board[n - 1][i] == 'O')
                uf.union(m * (n - 1) + i, dummy);
        }
        // 方向数组 d 是上下左右搜索的常用手法
        int[][] d = new int[][]{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
        for (int i = 1; i < n - 1; i++)
            for (int j = 1; j < m - 1; j++)
                if (board[i][j] == 'O')
                    // 将此 O 与上下左右的 O 连通
                    for (int k = 0; k < 4; k++) {
                        int x = i + d[k][0];
                        int y = j + d[k][1];
                        if (board[x][y] == 'O')
                            uf.union(x * m + y, i * m + j);
                    }
        // 所有不和 dummy 连通的 O，都要被替换
        for (int i = 1; i < n - 1; i++)
            for (int j = 1; j < m - 1; j++)
                if (!uf.connected(dummy, i * m + j))
                    board[i][j] = 'X';
    }



    /*===========================================================================================================================
     *990. 等式方程的可满足性
     * 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，
     * 并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
     * 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
     * 解法：将 equations 中的算式根据 == 和 != 分成两部分，先处理 == 算式，使得他们通过相等关系各自勾结成门派；然后处理 != 算式，检查不等关系是否破坏了相等关系的连通性。
     *  */
    public boolean equationsPossible(String[] equations) {
        //将26个字母当作节点
        UnionFind uf=new UnionFind(26);
        //先让==联通
        for (String es:equations) {
            if(es.charAt(1)=='='){
                uf.union(es.charAt(0)-'a',es.charAt(3)-'a');
            }
        }
        // 检查不等关系是否打破相等关系的连通性
        for (String es:equations) {
            if (es.charAt(1)=='!'&&uf.connected(es.charAt(0)-'a',es.charAt(3)-'a')){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board=new char[][]{{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}};
        Solution_10UF obj=new Solution_10UF();
        obj.solve(board);
        int n=board.length;
        int m= board[0].length;
        for (int i = 0; i < n; i++) {
            System.out.println(board[i]);
        }

    }
}
